package leetcode.primary;

import java.util.ArrayList;
import java.util.List;

public class T229 {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int cardNum1 = nums[0],count1=0;
        int cardNum2 = nums[0],count2=0;
        for (int num : nums) {
            //投票阶段，只要有一个投票，直接进入下一个
            //只当都不是投两个的时候才count--
            if (cardNum1==num){
                count1++;
                continue;
            }
            if (cardNum2==num){
                count2++;
                continue;
            }
            if (count1==0){
                cardNum1 = num;
                count1+=1;
                continue;
            }
            if (count2==0){
                cardNum2 = num;
                count2+=1;
                continue;
            }

            count1--;
            count2--;
        }

        //验证候选者是否符合
        count1=0;
        count2=0;
        for (int num : nums) {
            if (num==cardNum1){
                count1++;
            }else if (num==cardNum2){
                count2++;
            }
        }
        if (count1>nums.length/3){
            ans.add(cardNum1);
        }
        if (count2>nums.length/3){
            ans.add(cardNum2);
        }
        return ans;
    }

    public static void main(String[] args) {
        T229 t229 = new T229();
        List<Integer> list = t229.majorityElement(new int[]{0,3,4,0});
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }
}
